{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# User's Guide, Chapter 5: Lists of Lists, Functions, and Recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the last Chapter, we discussed Python Lists, how the :class:`~music21.stream.Stream`\n",
    "object is similar to a List, and how we can put :class:`~music21.note.Note` objects into a\n",
    "`Stream`, look at their offsets, and `.show()` the `Stream` in MusicXML or as text.  We\n",
    "ended by putting one `Stream` inside another `Stream`, which seemed like a neat trick\n",
    "until we discovered that we couldn't get at the elements inside the inner `Stream`.\n",
    "\n",
    "In this chapter we will work on how to exploit the power of nested `Streams`.  We'll\n",
    "begin with a discussion of recursive lists (since `Streams` work a lot like lists).\n",
    "Those with some programming will probably want to skip to the following section."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lists of Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lists (similar to Arrays in other languages) can hold all sorts of other things inside them\n",
    "including other lists.  So let's begin by creating two lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "listA = [10, 20, 30]\n",
    "listB = [1, 2, 3, listA]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now when we look at listB, we'll see that listA is inside it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, [10, 20, 30]]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "listB"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that when we look at the length (`len()`) of listB it shows that there are\n",
    "4 elements, not 6:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(listB)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's because the fourth element of listB (which, you'll recall, is called\n",
    "`listB[3]` not `listB[4]`) is itself a list, listA:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10, 20, 30]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "listB[3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "listB[3] is listA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So if we want to get the third element of listA, there is an easy way to do it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "listA[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But we can also think that `30` is also the third element *of the fourth element* of\n",
    "listB.  So we can write this instead:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "listB[3][2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oh, and since each of these is the last elements of their respective lists, we could\n",
    "instead write:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "listB[-1][-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "which means \"get the last element of the last element of listB\"\n",
    "\n",
    "But what if we just wanted to know every number stored anywhere in listB, even if\n",
    "that number is inside a list itself?  This won't work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "[10, 20, 30]\n"
     ]
    }
   ],
   "source": [
    "for number in listB:\n",
    "    print(number)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead, we have to test to see if each \"number\" in `listB` is actually a number or\n",
    "a list.  And if it's a list, we should find each number in that and print it instead.\n",
    "Here's a slightly more complicated set of commands to do that (remember, don't type\n",
    "the >>> or ... ; they'll appear automatically in Python's shell):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "10\n",
      "20\n",
      "30\n"
     ]
    }
   ],
   "source": [
    "for thing in listB:\n",
    "    if isinstance(thing, list):\n",
    "        for number in thing:\n",
    "            print(number)\n",
    "    else:\n",
    "        print(thing)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That did it!  How does it work?  Well we look at each \"thing\" in `listB` -- we\n",
    "call it \"thing\" here, because we're not sure if it's a number of a list.  Then\n",
    "in the next line ``if isinstance(thing, list):`` checks if the thing is a list.\n",
    "If that is `True` then we get to an inner loop, where we look at \"thing\" (which\n",
    "in this case is `listA`, but the program doesn't know that) and get the\n",
    "\"number\" from it.  But if \"thing\" is not a list, that's where the ``else`` comes\n",
    "in, which is what we run if we don't have a list, which just says, print the number.  \n",
    "(We're assuming in this case that there are only two types of things in `listB`, \n",
    "numbers and other lists.)  If you get an error, be sure not to forget the ending \":\" or to indent the next line.\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Functions and Recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But what if we did this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "listC = [100, 200, 300, listB]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now since listB contains listA, we end up with a list within a list within a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[100, 200, 300, [1, 2, 3, [10, 20, 30]]]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "listC"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we wanted to print all the numbers\n",
    "in listC, we could write an ugly set of commands like this one (I'll understand if \n",
    "you don't actually want to type this and just want to trust me that this works):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100\n",
      "200\n",
      "300\n",
      "1\n",
      "2\n",
      "3\n",
      "10\n",
      "20\n",
      "30\n"
     ]
    }
   ],
   "source": [
    "for thing in listC:\n",
    "    if isinstance(thing, list):\n",
    "        for innerThing in thing:\n",
    "            if isinstance(innerThing, list):\n",
    "                for number in innerThing:\n",
    "                    print(number)\n",
    "            else:\n",
    "                print(innerThing)\n",
    "    else:\n",
    "        print(thing)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Whew!  If this were the only way to do it, I wouldn't blame you if you decided\n",
    "that programming just wasn't worth the headache.  Especially since you've probably\n",
    "already guessed that we could make: ``listD = [4, 5, listC, 6, 7]`` and get another\n",
    "layer of lists.  Fortunately, there's a little bit of programming magic called\n",
    "\"recursion\" that we can use to get to the heart of the matter.  Notice that in the\n",
    "code I just wrote, there are a few lines that are basically the same (with a few\n",
    "words changed) as other parts of the code.  With recursive coding, we'll find a way\n",
    "to save those lines to reuse them.  Type these six lines:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def flatPrint(myList):\n",
    "    for thing in myList:\n",
    "        if isinstance(thing, list):\n",
    "            flatPrint(thing)\n",
    "        else:\n",
    "            print(thing)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What we've done is created a new function called ''flatPrint'' which reaches into lists\n",
    "of lists and prints anything that is in them.  \n",
    "\n",
    "Now try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100\n",
      "200\n",
      "300\n",
      "1\n",
      "2\n",
      "3\n",
      "10\n",
      "20\n",
      "30\n"
     ]
    }
   ],
   "source": [
    "flatPrint(listC)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It works! But how?  Here's how functions work in general (skip this, if you know all about\n",
    "functions):\n",
    "\n",
    "The `def` statement says that we're going to ''define'' a new function.  After the\n",
    "word `def` comes the name of the function -- something we'll be able to call it to \n",
    "use it later. (We call the process of taking nested\n",
    "structures and turning them into something linear \"flattening\" them, like crushing a\n",
    "cardboard box.  Since this is a flattener that also prints what's inside it, `flatPrint`\n",
    "is a good name for it.  Notice that just like with variables, case matters in Python, \n",
    "so `flatPrint` isn't the same as `flatprint` or `Flatprint` or `FlAtPrInT`.)\n",
    "\n",
    "After \"flatPrint\", within parentheses comes the variable name `myList`.  Notice that\n",
    "we haven't used the name `myList` yet -- it doesn't exist.  What `myList` means here\n",
    "is that any time we use the function `flatPrint`, whatever the name of the list was,\n",
    "within `flatPrint` it will be called `myList`.  So you could say `flatPrint(listC)`,\n",
    "as we just did, and within the function `flatPrint`, `listC` will be known as `myList`.\n",
    "\n",
    "Here's a simpler function that will explain that better.  `squareMe` \n",
    "takes in a number and prints its square:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def squareMe(number):\n",
    "    print(number * number)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100\n"
     ]
    }
   ],
   "source": [
    "squareMe(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6.25\n"
     ]
    }
   ],
   "source": [
    "squareMe(2.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9.8596\n"
     ]
    }
   ],
   "source": [
    "pi = 3.14\n",
    "squareMe(pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice two things in the last case.  First that pi isn't exactly 3.14 -- we all know that;\n",
    "I just wanted to make sure the math teachers in the room didn't go into conniptions.  Second\n",
    "that we gave the variable `pi` to the function `squareMe`.  But within the function `squareMe` we \n",
    "didn't write: ``print(pi * pi)``; instead within the function, `pi` (or any other variable\n",
    "or number) will simply be called `number`.  (By the way, instead of writing ``print(number * number)``\n",
    "we could have written ``print(number**2)`` since '' \\*\\* '' is how Python denotes exponents).    \n",
    "\n",
    "At the end of a function, you can either `print` something out, or `return` a value, which can\n",
    "be used for anything else.  Here's ``cubeMe`` which works a lot like ``squareMe``, but it cubes\n",
    "the number and instead of printing it, it returns it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cubeMe(number):\n",
    "    return number * number * number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Because we're not printing `number`, we can assign the value of cubeMe to another variable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = cubeMe(2)\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "512"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = cubeMe(x)\n",
    "y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that if ``x = cubeMe(2)`` and ``y = cubeMe(x)`` then we can substitute ``cubeMe(2)`` for\n",
    "\t`x` and write:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "512"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = cubeMe(cubeMe(2))\n",
    "y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus, using `return` instead of `print` is more powerful, so after finishing with `flatPrint`, we'll mostly write `return` and not `print` functions.\n",
    "\n",
    "So, getting back to `flatPrint`, which you'll recall is (I'm adding commented line numbers again so I can refer to them):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def flatPrint(myList):              # 1\n",
    "    for thing in myList:            # 2\n",
    "        if isinstance(thing, list): # 3\n",
    "            flatPrint(thing)        # 4\n",
    "        else:                       # 5\n",
    "            print(thing)            # 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at it line by line.  \n",
    "\n",
    "Line 1, as we said, defines the function called `flatPrint` which\n",
    "expects a list which we'll call `myList`.\n",
    "\n",
    "Line 2, says \"for each thing that is inside myList, grab it and call it `thing`.\"\n",
    "Once we're done with `thing`, the program will jump back to line 2 to get the next thing.\n",
    "\n",
    "Line 3, checks if `thing` is a list.  If so, we do line 4.  If not we jump to line 5.\n",
    "\n",
    "Line 4: This is where the magic happens.  We know now that `thing` is a list.  So how do\n",
    "we print a list (which might have other lists inside of it)? We use `flatPrint`!  In essence\n",
    "`flatPrint` uses its own power of discerning between lists and numbers to print any internal\n",
    "lists.  We call functions that use (\"call\") themselves *recursive functions* and the process\n",
    "of using recursive functions is called *recursion*.  It's a powerful tool and one we'll use\n",
    "in music21 a lot.\n",
    "\n",
    "Line 5, is where we jump to from line 3 if `thing` is not a list, so then Python executes line 6\n",
    "\n",
    "Line 6, simply prints `thing`, which we know by now is a number.\n",
    "\n",
    "A warning: unlike some programming languages (Java, C, etc.), Python never checks that what you\n",
    "pass to `flatPrint` actually is a list.  So you can try doing something like ``flatPrint(30)``\n",
    "but since `30` isn't a list, you'll get an error:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "tags": [
     "nbval-raises-exception"
    ]
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'int' object is not iterable",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-26-d6916f79680c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mflatPrint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m30\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-25-910b883fde2e>\u001b[0m in \u001b[0;36mflatPrint\u001b[0;34m(myList)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mflatPrint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmyList\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m              \u001b[0;31m# 1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m     \u001b[0;32mfor\u001b[0m \u001b[0mthing\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mmyList\u001b[0m\u001b[0;34m:\u001b[0m            \u001b[0;31m# 2\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      3\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mthing\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mlist\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m# 3\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m             \u001b[0mflatPrint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mthing\u001b[0m\u001b[0;34m)\u001b[0m        \u001b[0;31m# 4\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m         \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m                       \u001b[0;31m# 5\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: 'int' object is not iterable"
     ]
    }
   ],
   "source": [
    "flatPrint(30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For more information on data structures (lists, lists of lists, and things we didn't get to,\n",
    "I suggest watching Google's <a href=\"http://code.google.com/edu/languages/google-python-class/\">Python tutorial</a>,\n",
    "especially class 2)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Wrapup"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this chapter we looked at how we can look inside lists of lists, which will be\n",
    "important when we consider how to work with `Streams` of `Streams` in music21, to look\n",
    "at `Measures` within `Parts` within a `Score`.  We also learned how to define a function\n",
    "and write recursive functions to do powerful work in just a few lines of code.  In the\n",
    "next chapter we apply all this to music with :ref:`Streams of Streams <usersGuide_06_stream2>`."
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
